class Solution 
{
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        //排序
        sort(nums.begin(), nums.end());
        
        int n = nums.size();
        vector<vector<int>> ret;

        for(int i = 0; i < n; )
        {
            //利用双指针
            int left = i + 1,right = n -1,target = -nums[i];
            if(nums[i] > 0) break;
            while(left < right)
            {
                int sum = nums[left] + nums[right];
                if(sum > target) right--;
                else if(sum < target) left++;
                else
                {
                    ret.push_back({nums[i],nums[left], nums[right]});
                    left++;
                    right--;
                //去重
                while(left < right && nums[left] == nums[left - 1])
                    left++;
                while(left < right && nums[right] == nums[right + 1])
                    right--;
                }
            }
            //去重
            i++;
            while(i < n && nums[i] == nums[i - 1])   
                i++;
        }

        return ret;
    }
};

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        int n = nums.size();

          for(int i = 0;i < n; )
          {
                for(int j = n - 1;j >= 0;)
                {
                    int left = i + 1, right = j - 1;
                    long long sum1 = nums[i] + nums[j];  
                    while(left < right)
                    {
                        long long sum2 = nums[left] + nums[right];

                        if(sum1 + sum2 > target)
                            right--;
                        else if(sum1 + sum2 < target)
                            left++;
                        else
                        {
                            ret.push_back({nums[i],nums[j],nums[left],nums[right]});
                            left++,right--;

                            //去重
                            while(left < right && nums[left] == nums[left - 1]) 
                                left++;
                            while(left < right && nums[right] == nums[right + 1]) 
                                right--;
                        }
                    }
                    j--;
                    while(j >= 0 && nums[j] == nums[j + 1]) 
                        j--;
                }
                i++;
                while(i < n && nums[i] == nums[i - 1])
                    i++;
          }


        return ret;
    }
};

class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        //用数组模拟hash表
        int hash[128] = {0};

        int len = s.size(),ret = 0;

        //利用滑动窗口
        for(int left = 0, right = 0;right < len; right++)  
        {
            hash[s[right]]++;//进窗口
            while(hash[s[right]] > 1)//判断
            {
                hash[s[left++]]--;//出窗口
            }
            ret = max(ret,right - left + 1);//更新结果
        }
        return ret;
    }
};

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) 
    {
        int n = nums.size(),left = 0, right = 0,ret = 0;
        int hash[2] = {0};//模拟hash
        while(right < n)
        {
            hash[nums[right]]++;//进窗口
            while(hash[0] > k)//判断
            {
                hash[nums[left++]]--;
            }
            ret = max(ret,right - left + 1);
            right++;
        }
        return ret;
    }
};
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        //处理边界情况
        if(nums.size() == 0)
            return {-1,-1};
        //利用二分查找-查找左/右边界
        int n = nums.size(),lIndex = 0,left = 0, right = n - 1;
        //查找左边界
        while(left < right)
        {
            int mid = left + (right - left) / 2; // 防溢出写法

            if(nums[mid] >= target) right = mid; 
            else if(nums[mid] < target) left = mid + 1;
        }   
        if(nums[left] != target)
            return {-1,-1};
        lIndex = left;


        //查找右边界
        left = 0, right = n - 1;
        while(left < right)
        {
            int mid = left + (right - left + 1) / 2; // 防溢出写法

            if(nums[mid] > target) right = mid - 1;
            else if(nums[mid] <= target) left = mid;
        }
        if(nums[right] != target)
            return {-1,-1};
        else
            return {lIndex,left};
    }
};